package com.datastructure.test.editordistance;

import java.util.Arrays;

public class EditorDistance {

    public static void main(String[] args) {
        EditorDistance editorDistance = new EditorDistance();
        String s1 = "nowcoder";
        String s2 = "new";
        int editDistance = editorDistance.editDistance(s1, s2);
        System.out.println(editDistance);
    }

    public int editDistance (String str1, String str2) {
        // write code here
        int len1 = str1.length(); // 获取 str1 的长度
        int len2 = str2.length(); // 获取 str2 的长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        for(int i=1; i<=str1.length(); i++){
            for(int j=1; j<=str2.length(); j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){  //第一种情况
                    dp[i][j] = dp[i-1][j-1];
                }else{  //第二种情况
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i][j-1]))+1;  //状态转移方程
                }
            }
        }
        return dp[str1.length()][str2.length()];
    }
}
